package erfen.base;

import java.util.Arrays;

/**
 * 1.在 升序且不重复 的数组里找某个值 → 返回下标，找不到返回 -1
 * 2.在 升序可重复 的数组里找某个值 → 返回最左侧/最右侧下标
 * 3.在 升序可重复 的数组里找 “>= target 的最小值”
 */
public class BaseDemo {
    /**
     * 优化后的二分查找实现（查找目标值的插入位置或精确匹配）
     */
    public static int binarySearch(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while (left<=right){
            int mid=(left+right)>>>1;
            if(nums[mid]>=target)
                right=mid-1;
            else left=mid+1;
        }
        return left;
    }

    public static int searchUnique(int[] nums, int target) {
        int pos = binarySearch(nums, target);
        return (pos < nums.length && nums[pos] == target) ? pos : -1;
    }

    public static int findLast(int[] nums, int target) {
        int pos = binarySearch(nums, target + 1) - 1;
        return (pos >= 0 && nums[pos] == target) ? pos : -1;
    }

    public static void main(String[] args) {
        // 标准二分查找测试
        System.out.println("标准二分查找测试:");
        testCase(new int[]{1, 3, 5, 7}, 3, 1);
        testCase(new int[]{2, 4, 6, 8, 10}, 7, -1);
        testCase(new int[]{5}, 5, 0);
        testCase(new int[]{}, 0, -1);

        // 重复数组边界查找测试
        System.out.println("\n重复数组边界查找测试:");
        testBoundary(new int[]{1, 3, 3, 5, 7}, 3);
        testBoundary(new int[]{1, 1, 1, 1}, 1);

        // 插入位置测试（lower_bound）
        System.out.println("\n插入位置测试:");
        testInsert(new int[]{1, 3, 3, 5, 7}, 0, 0);
        testInsert(new int[]{1, 3, 3, 5, 7}, 4, 3);
        testInsert(new int[]{1, 3, 3, 5, 7}, 9, 5);
    }

    // 标准测试用例模板
    private static void testCase(int[] nums, int target, int expected) {
        int result = searchUnique(nums, target);
        System.out.printf("数组: %s, 目标: %d => 结果: %d (预期: %d) %s\n",
                Arrays.toString(nums), target, result, expected,
                result == expected ? "✓" : "✗");
    }

    // 边界查找测试模板
    private static void testBoundary(int[] nums, int target) {
        int left = binarySearch(nums, target);
        int right = findLast(nums, target);
        boolean valid = (left <= right) &&
                (left < nums.length && nums[left] == target) &&
                (right >= 0 && nums[right] == target);
        System.out.printf("在 %s 中查找 %d => 最左:%d, 最右:%d %s\n",
                Arrays.toString(nums), target, left, right,
                valid ? "✓" : "✗");
    }

    // 插入位置测试模板
    private static void testInsert(int[] nums, int target, int expected) {
        int result = binarySearch(nums, target);
        System.out.printf("在 %s 中查找 %d => %d (预期: %d) %s\n",
                Arrays.toString(nums), target, result, expected,
                result == expected ? "✓" : "✗");
    }
}
